/*******************************************************************************
 * Copyright (c) 2010, 2030 www.mahao.cn
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 *******************************************************************************/
package cn.itlaobing.sort;

/** 
 * ClassName: QuickSort <br/> 
 * Function: 快速排序 <br/> 
 * date: 2017年6月12日 上午9:38:50 <br/> 
 * 
 * @author Mmmmm 
 * @version  
 * @since JDK 1.8 
 */
public class QuickSort {
		  
		 int a[]={22,20,26,24,28,25,23,21,27,29};  
		
		public void quickSort(){  
		    quick(a);  
		    for(int i=0;i<a.length;i++){  
		       System.out.print(a[i]+"   ");  
		    }  
		}  
		public int getMiddle(int[] list, int low, int high) {    
		            int tmp =list[low];    //数组的第一个作为中轴    
		            while (low < high){    
		                while (low < high&& list[high] >= tmp) {    
		                   high--;    
		                }    
		  
		                list[low] =list[high];   //比中轴小的记录移到低端    
		                while (low < high&& list[low] <= tmp) {    
		                    low++;    
		                }    
		  
		                list[high] =list[low];   //比中轴大的记录移到高端    
		            }    
		           list[low] = tmp;              //中轴记录到尾    
		            return low;                   //返回中轴的位置    
		}   
		  
		public void _quickSort(int[] list, int low, int high) {    
		            if (low < high){    
		               int middle =getMiddle(list, low, high);  //将list数组进行一分为二    
		               _quickSort(list, low, middle - 1);       //对低字表进行递归排序    
		               _quickSort(list,middle + 1, high);       //对高字表进行递归排序    
		            }    
		}  
		  
		public void quick(int[] a2) {    
		            if (a2.length > 0) {    //查看数组是否为空    
		                _quickSort(a2,0, a2.length - 1);    
		            }    
		}  
}
